home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 050 / madtrb10.arc / TREE.DOC < prev    next >
Encoding:
Text File  |  1985-12-08  |  4.8 KB  |  110 lines
  1. The following is a Pascal assignment that I had in data structures.  It
  2. implements a doubly linked queue, a doubly linked circular queue, and a binary
  3. search tree for storing data using pointers.  It is probably of use to you if
  4. you want to learn something about the previously stated data structures and
  5. pointers.  Before digging into the code perhaps you want to get a book on
  6. data structures and read up on the above data structures.  Happy computing!!
  7.  
  8.                                                        Chris Maeder
  9.  
  10.  
  11.                        QUEUE AND TREE ASSIGNMENT
  12.  
  13.                            Data  Structures
  14.                                Fall 1985
  15.  
  16. Overview:
  17.  
  18.     In this assignment you will process mail orders for a sporting goods store.
  19.     You will use queues to hold the transactions waiting to be processed and a
  20.     binary search tree to hold the merchandise the store carries.  For the
  21.     queues and tree you must use the Pascal pointer type (linked list
  22.     implementation).
  23.  
  24.     Transactions are processed one day at a time.  At the end of every day,
  25.     print summary information.  At the very end of the program, print the
  26.     binary search tree.
  27.  
  28. Codes:
  29.  
  30.     The transaction codes are N, A, R, and S.  Additional codes are * and X.
  31.  
  32.          N   Insert a brand new item into the store's inventory.
  33.          A   Add a quantity to an existing item.
  34.          R   Remove an item from the store's inventory.
  35.          S   Sell a quantity of an existing item.
  36.          *   Add or delete a clerk.
  37.          X   Marks the end of a day.
  38.  
  39.     Exact syntax is as follows:
  40.  
  41.          N item_name quantity
  42.          A item_name quantity
  43.          R item_name
  44.          S item_name quantity
  45.          * HIRE clerk_name
  46.          * QUIT clerk_name
  47.          X day 1
  48.  
  49.     Note that you do not have to do any error checking for proper syntax, non-
  50.     existant codes, or whatever.  All input is correct.
  51.  
  52.     Item_names are a maximum of 20 characters.  Quantities are integers.
  53.     Clerk_names are a maximum of 25 characters.  The phrase after an X is just
  54.     there for readability of the data file.
  55.  
  56. Details on transaction processing:
  57.  
  58.     Each day N, A, R, and S codes may come in.  They will come in any order.
  59.     You will want to process the N and A transactions first so there are more
  60.     items and quantities for the sales.  S transactions should be done next
  61.     first come, first serve.  If a sale order cannot be filled, leave it on
  62.     the queue as the first sale order to be processed the following day.
  63.     R codes are processed last each day.  After an item is removed, if someone
  64.     tries to buy that item, it will not be there (you will have removed it
  65.     from the tree).
  66.  
  67.     As long as you use queues to hold transactions, you can use whatever
  68.     variety you like (e.g. doubly linked, one queue, 2, 3, 4, priority queue).
  69.     For each transaction processed, print an appropriate message.
  70.  
  71. Details on clerks:
  72.  
  73.     The clerks get bored doing mail order transactions so a rotating schedule
  74.     is set up.  Each clerk does just two transactions (N, A, R, or S codes).
  75.     Then the next clerk does two and so on.  If a new clerk is added to the
  76.     schedule with a HIRE command, he/she is added to the circular queue in the
  77.     spot behind the current head node (i.e. added to the end of the current
  78.     cycle to have time to learn the system).  Occasionally, clerks get fed up
  79.     with the job ad quit (QUIT).  They would be removed from the schedule at
  80.     the time of the QUIT command is read.  To facilitate deletions, use double
  81.     links for the circular list.
  82.  
  83.     At the end of every day, after the transactions for the day are printed,
  84.     print the list of current clerks.
  85.  
  86.     Also, print the name of the clerk who handled each transaction when you
  87.     print that transaction.
  88.  
  89. The store inventory:
  90.  
  91.     Rather than using heaps, sorted arrays, or hashing to keep the store
  92.     inventory, use a binary search tree.  You will need algorithms for
  93.     inserting into the tree, deleting from the tree, and searching the tree.
  94.     Also, at the very end of the program you will print all the items in the
  95.     tree in alphabetical order using a recursive inorder traversal.
  96.  
  97. Output:
  98.  
  99.     Output must be very clear and well spaced.  Output should be organized by
  100.     days.
  101.  
  102.     Print each transaction as it is processed.  As long as all input data is
  103.     output in a readable fashion, you do not have to exactly echo print it.
  104.     Also remember to print the clerk handling the transaction.  At the end of
  105.     every day, print a list of current clerks and print a list of items left
  106.     on the queue.
  107.  
  108.     At the very end, skip an appropriate number of lines and use a title before
  109.     printing the tree.  For 3 points extra credit, the tree may be printed in
  110.     tree form in addition to printing its contents in alphabetical order.